#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key, color;
    struct Node *lc, *rc;
} Node;

Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init() {
    NIL->key = 0;
    NIL->color = 1;
    NIL->lc = NIL->rc = NIL;
}

Node *gen(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->color = 0;
    p->lc = p->rc = NIL;
    return p;
}

int hasRed(Node *root) {
    return root->lc->color == 0 || root->rc->color == 0;
}

Node *lrt(Node *root) {
    Node *temp = root->rc;
    root->rc = temp->lc;
    temp->lc = root;
    return temp;
}

Node *rrt(Node *root) {
    Node *temp = root->lc;
    root->lc = temp->rc;
    temp->rc = root;
    return temp;
}

Node *insmod(Node *root) {
    if (!hasRed(root)) return root;
    int flag = 0;
    if (root->lc->color == 0 && root->rc->color == 0 &&
       (hasRed(root->lc) || hasRed(root->rc))) //发生冲突才调整
        goto insend;
    if (root->lc->color == 0 && hasRed(root->lc)) flag = 1;
    if (root->rc->color == 0 && hasRed(root->rc)) flag = 2;
    if (flag == 0) return root; //没有冲突
    if (flag == 1) {
        if (root->lc->rc->color == 0) {
            root->lc = lrt(root->lc);
        }
        root = rrt(root);
    } else {
        if (root->rc->lc->color == 0) {
            root->rc = rrt(root->rc);
        }
        root = lrt(root);
    }
insend:
    root->color = 0;
    root->lc->color = root->rc->color = 1;
    return root;
}

Node *__insert(Node *root, int key) {
    if (root == NIL) return gen(key);
    if (key == root->key) return root;
    if (key < root->key) {
        root->lc = __insert(root->lc, key);
    } else {
        root->rc = __insert(root->rc, key);
    }
    return insmod(root);
}

Node *insert(Node *root, int key) {
    root = __insert(root, key);
    root->color = 1;
    return root;
}

Node *delmod(Node *root) {
    if (root->lc->color != 2 && root->rc->color != 2) return root;
    if (hasRed(root)) {
        int flag = 0;
        root->color = 0; //原根节点改红
        if (root->lc->color == 0) {
            root = rrt(root); flag = 1;
        } else {
            root = lrt(root); flag = 2;
        }
        root->color = 1; //新根节点改黑
        if (flag == 1) root->rc = delmod(root->rc);
        else root->lc = delmod(root->lc);
        return root;
    }
    if (root->lc->color == 2 && !hasRed(root->rc) ||
       (root->rc->color == 2 && !hasRed(root->lc)))
    {
        root->lc->color -= 1;
        root->rc->color -= 1;
        root->color += 1;
        return root;
    } 
    if (root->lc->color == 2) {
        root->lc->color = 1;
        if (root->rc->rc->color != 0) {
            root->rc->color = 0;
            root->rc = rrt(root->rc);
            root->rc->color = 1;
        }
        root = lrt(root);
        root->color = root->lc->color;
    } else {
        root->rc->color = 1;
        if (root->lc->lc->color != 0) {
            root->lc->color = 0;
            root->lc = lrt(root->lc);
            root->lc->color = 1;
        }
        root = rrt(root);
        root->color = root->rc->color;
    }
    root->lc->color = root->rc->color = 1;
    return root;
}

Node *pred(Node *root) {
    Node *temp = root->lc;
    while (temp->rc != NIL) temp = temp->rc;
    return temp;
}

Node *__erase(Node *root, int key) {
    if (root == NIL) return NIL;
    if (key < root->key) {
        root->lc = __erase(root->lc, key);
    } else if (key > root->key) {
        root->rc = __erase(root->rc, key);
    } else {
        if (root->lc == NIL || root->rc == NIL) {
            Node *temp = root->lc != NIL ? root->lc : root->rc;
            temp->color += root->color;
            free(root);
            return temp;
        }
        Node *temp = pred(root);
        root->key = temp->key;
        root->lc = __erase(root->lc, temp->key);
    }
    return delmod(root);
}

Node *erase(Node *root, int key) {
    root = __erase(root, key);
    root->color = 1;
    return root;
}

void print(Node *root) {
    printf("%d %d %d %d\n", 
           root->key, root->color,
           root->lc->key, root->rc->key
    );
}

void output(Node *root) {
    if (root == NIL) return ;
    output(root->lc);
    print(root);
    output(root->rc);
    return ;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->lc);
    clear(root->rc);
    free(root);
    return ;
}

int main() {
    int op, val;
    Node *root = NIL;
    while (~scanf("%d%d", &op, &val)) {
        switch (op) {
            case 1: root = insert(root, val); break;
            case 2: root = erase(root, val); break;
        }
        output(root);
        printf("-------------------\n");
    }
    clear(root);
    return 0;
}
